package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.Graph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.weight.WeightedPath
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.model.InMemoryWeightedPath
import org.apache.commons.graph.weight.Monoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * The predecessor list is a list of vertex of a [org.apache.commons.graph.Graph].
 * Each vertex' entry contains the index of its predecessor in a path through the graph.
 *
 * @param <V> the Graph vertices type
 * @param <WE> the Graph weighted edges type
 * @param <W> the weight type
</W></WE></V> */
class PredecessorsList<V, WE, W>(
    private val graph: Graph<V, WE>,
    private val weightOperations: Monoid<W>,
    private val weightedEdges: Mapper<WE, W>) {

    private val predecessors: MutableMap<V, V> = HashMap()

    /**
     * Add an edge in the predecessor list associated to the input vertex.
     *
     * @param tail the predecessor vertex
     * @param head the edge that succeeds to the input vertex
     */
    fun addPredecessor(tail: V, head: V) {
        predecessors[tail] = head
    }

    /**
     * Build a [WeightedPath] instance related to source-target path.
     *
     * @param source the path source vertex
     * @param target the path target vertex
     * @return the weighted path related to source to target
     */
    fun buildPath(source: V, target: V): WeightedPath<V, WE, W> {
        val path = InMemoryWeightedPath(source, target, weightOperations, weightedEdges)

        var vertex = target
        while (source != vertex) {
            val predecessor = predecessors[vertex]
                ?: throw PathNotFoundException(
                    "Path from '%s' to '%s' doesn't exist",
                    source,
                    target
                )
            val edge = graph.getEdge(predecessor, vertex)!!

            path.addConnectionInHead(predecessor, edge, vertex)

            vertex = predecessor
        }

        return path
    }

    /**
     * Build a [WeightedPath] instance related to source-target path.
     *
     * @param source the path source vertex
     * @param touch the node where search frontiers meet, producing the shortest path
     * @param target the path target vertex
     * @param backwardsList the predecessor list in backwards search space along reversed edges
     * @return the weighted path related to source to target
     */
    fun buildPath(source: V, touch: V, target: V, backwardsList: org.apache.commons.graph.algorithms.shortestpath.PredecessorsList<V, WE, W>): WeightedPath<V, WE, W> {
        val path = InMemoryWeightedPath(source, target, weightOperations, weightedEdges)

        var vertex = touch
        while (source != vertex) {
            val predecessor = predecessors[vertex]
                ?: throw PathNotFoundException(
                    "Path from '%s' to '%s' doesn't exist",
                    source,
                    target
                )
            val edge = graph.getEdge(predecessor, vertex)!!

            path.addConnectionInHead(predecessor, edge, vertex)

            vertex = predecessor
        }

        vertex = touch

        while (target != vertex) {
            // 'predecessor' is actually a successor.
            val predecessor = backwardsList.predecessors[vertex]
                ?: throw PathNotFoundException(
                    "Path from '%s' to '%s' doesn't exist",
                    source,
                    target
                )
            val edge = graph.getEdge(vertex, predecessor)!!

            path.addConnectionInTail(vertex, edge, predecessor)

            vertex = predecessor
        }

        return path
    }

    val isEmpty: Boolean
        /**
         * Checks the predecessor list has no elements.
         *
         * @return true, if the predecessor list has no elements, false otherwise.
         */
        get() = predecessors.isEmpty()
}
